package Class023;

import Class021.Merge;
import Utils.ArrayUtils;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        test();
    }

    public static int[] partition(int[] arr, int l, int r, int pivot) {
        int less = l - 1, more = r + 1, index = l;
        while (index < more) {
            if (arr[index] < pivot) {
                ArrayUtils.swap(arr, index++, ++less);
            } else if (arr[index] > pivot) {
                ArrayUtils.swap(arr, index, --more);
            } else {
                index++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    //这个随机过程具有一定的常数时间
    //但是为了将快排收敛到O(N * logN), 需要加上这一行。
    //下面的测试方法也很明显，若不加，那么时间确实要比加上快
    //但是不加的最差时间复杂度是O(N^2)，空间复杂度O(N),因为要开N层递归栈
    public static void qs(int[] arr, int l, int r) {
        if (l >= r) return;
        int pivot = arr[(int) (Math.random() * (r - l + 1)) + l];
        int[] range = partition(arr, l, r, pivot);
        qs(arr, l, range[0] - 1);
        qs(arr, range[1] + 1, r);
    }

    public static void randomQuickSort(int[] arr) {
        qs(arr, 0, arr.length - 1);
    }

    public static void test() {
        int time = 1000;
        int amount = 10000, max = 1000;
        int errTime = 0;
        System.out.println("Correctness Test:");
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            int[] m = Arrays.copyOf(base, base.length);
            int[] q = Arrays.copyOf(base, base.length);
            Merge.myMerge(m, true);
            randomQuickSort(q);
            if (!ArrayUtils.judge(q, m)) {
                System.out.println(Arrays.toString(base));
                System.out.println("Should be:");
                System.out.println(Arrays.toString(q));
                System.out.println("Wrong answer:");
                System.out.println(Arrays.toString(m));
                errTime++;
            }
        }
        if (errTime == 0) {
            System.out.println("All clear.");
        } else {
            System.out.println("Errors:" + errTime + "/" + time);
            System.out.println("Accuracy:" + (time - errTime) * 1.0 / time);
            return;
        }

        System.out.println("Time test:");
        long s, e;
        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            Merge.myMerge(base, true);
        }
        e = System.currentTimeMillis();
        System.out.println("Merge(Rec):" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            randomQuickSort(base);
        }
        e = System.currentTimeMillis();
        System.out.println("Random Quick Sort:" + (e - s) + "ms");
    }
}
